package com.gali.leetcode.day7;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @Auther: gali
 * @Date: 2022-07-20 19:35
 * @Description:删除链表的倒数第 N 个结点
 */
public class Solution {
    /**
     * 链表
     */
    public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

    /**
     * 利用快慢指针的方式来解决
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //定义一个伪指针，用于返回结果
        ListNode pre = new ListNode(0);
        pre.next=head;
        //快节点，用于遍历链表
        ListNode start = pre;
        //慢节点
        ListNode end = pre;
        //遍历链表，用于快节点先移动n步
        while (n!=0){
            start=start.next;
            n--;
        }
        //当快节点遍历到末尾了就停止，此时慢节点刚好到了要删除的节点的前节点
        while (start.next!=null){
            start=start.next;
            end=end.next;
        }
        end.next=end.next.next;
        return pre.next;
    }

    /**
     * 有效的括号(栈的思想)
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        int length = s.length();
        if (length<=0||length%2==1){
            return false;
        }
        Map<Character,Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        //定义一个栈
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            char key = s.charAt(i);
            if (map.containsKey(key)){
                //isEmpty()判断栈是否为空,
                // peek()函数返回栈顶的元素,
                // pop()函数返回栈顶的元素，并且将该栈顶元素出栈。
                if (stack.isEmpty()||stack.peek()!=map.get(key)){
                    return false;
                }
                stack.pop();
            }else {
                //没有就入栈
                stack.push(key);
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Map<Character,Character> map = new HashMap<>();
        map.put('1','2');
        map.containsKey('1');
        map.containsValue('2');
        System.out.println(map.containsKey('1'));
        System.out.println(map.containsValue('2'));

    }
}
